유니온 파인드

유니온 파인드(Union Find)

그래프 알고리즘의 종류로 '합집합 찾기'라는 의미를 가지고 있다.
상호 배타적 집합(Disjoint set)이라고도 불린다.
노드의 루트 노드를 찾는 Find 과정과 노드를 합치는 Union 과정, 총 2가지 연산으로 이루어져 있다.
두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
트리 구조로 이루어져 있다.
구현이 간단하고 동작 속도가 매우 빠르기 때문에 다른 알고리즘의 일부로 자주 사용된다.

그래프의 연결성을 확인하는 크루스칼 알고리즘이나 가장 큰 집합을 추적하는데 Union-Find를 적용할 수 있다.

파인드 과정(Find)

원하는 노드의 루트 노드를 찾는 과정이다.

<잘못된 예시>

int find(int x){
    if (x == parent[x]){
        return x;
    }
    else {
        return find(parent[x]);
    }
}

자신이 루트 노드이면 자기 자신을 return 한다.

그렇지 않다면 자신 부모가 루트 노드인지 확인한다.

하지만 위의 코드의 경우 문제점이 발생한다.

Find과정_1

위 그림과 같이 한쪽으로 치우쳐진 tree의 경우 루트 노드를 찾는데 O(N)의 시간복잡도가 걸리게 된다.

int find(int x){
    if (x == parent[x]){
        return x;
    }
    else{
        return parent[x]=find(parent[x]);
    }
}

위 코드대로 하게 되면 루트노드를 찾게 되면 x의 부모를 바로 루트노드로 바꾸어 주어 아래의 그림과 같이 바꿔지게 됩니다. 이로써 find의 효율이 높아지게 된다.

Find과정_2

Find 함수의 시간 복잡도는 트리 형태의 그래프이기 때문에 O(logN)이 된다.

배열로 표현한 경우에는 O(N)만큼 걸리기 때문에 트리 형태의 그래프로 하는것이 효율적이다.

유니온 과정(Union)

매개변수로 두 개의 값을 받아서 두 노드가 포함되어 있는 각각의 집합을 합쳐줘야한다.

하나의 예시로 y의 집합을 x의 집합에 합쳐보자.

<잘못된 예시>

void union(int x,int y){
    x = find(x);
    y = find(y);
    if (x!=y)
        parent[y] = x;
}

find 함수를 사용하여 각각의 root를 찾고, 두 집합의 루트가 다른 경우 y의 부모노드를 x로 바꿔주었다.

하지만 높이가 높은 트리가 높이가 낮은 트리 밑으로 들어가게 되면 트리가 더 깊어지게 된다. 따라서 트리의 높이가 낮은 트리가 트리의 높이가 높은 트리 밑으로 들어가야 한다.

이를 위해 트리의 높이를 기록해 두는 rank 배열을 추가한다.

<union-by-rank 기법>

void union(int x, int y){
    x = find(x);
    y = find(y);
  
    if (x == y)
    return;
  
    if (rank[x] > rank[y]){
        parent[y] = x;
        rank[x] += rank[y];
    }
    else {
    parent[x] = y;
        rank[y] += rank[x];
    }
}

find 함수로 각각의 루트 노드를 찾고난 후 만약 루트 노드가 같다면 return 해주고

루트노드가 다르다면 높이가 높은 트리에 높이가 낮은 트리를 붙여준다.

Find 함수의 시간 복잡도는 트리 형태의 그래프이기 때문에 O(logN)이 된다.

무게를 고려한 유니온 과정(Weighted Union)

위의 경우에는 parent 배열과 size 배열이 존재해서 메모리를 두 배로 사용하게 된다. 이를 개선하고자 나온 방법이 바로 Weighted Union Find 방법이다.

parent 배열은 음수일 경우에 부모노드로서 음수의 절대값이 size 되고, 양수일 경우에는 부모노드를 가리키게 된다.

예를 들어, parent[2] = -2 일 경우에 2번 노드 밑에 1개의 노드가 더 있어서 총 2개의 노드가 존재한다는 의미이고, parent[4] = 6 일 경우에는 4번 노드의 부모가 6번 노드라는 의미이다.

int parent[MAX_SIZE];

for (int i=0; i<MAX_SIZE; i++)
    parent[i] = -1;

int find(int x){
    if (parent[x] < 0){
        return x;
    }
    else{
        int y = find(parent[x]);
        parent[x] = y;
        return y;
    }
}

void union(int x, int y){
    x = find(x);
    y = find(y);
  
    if (x == y)
        return;
  
    // parent[x], parent[y] 값은 음수이므로 값이 작은 경우가 더 높이가 큰 노드이다.
    if (parent[x] < parent[y]){
        parent[x] += parent[y];
        parent[y] = x;
    }
    else {
        parent[y] += parent[x];
        parent[x] = y;
    }
}